#ifndef retrospec_game_astar
#define retrospec_game_astar

//header for astar algorithm
#define for if( false ) {} else for

#define MAX_CHILDREN    8

//*  A * class   

//steps for using
/*	1. create new AstarClass passing in a 1/0 array represent the map (0=open, 1=blocked)
	2. To start a path, call NewPath(...) followed by GetNodeX/GetNodeY to get the
		location of the tile element
	3. When a path has been found (step 2) and we wish to simply get the next one
		use PathNextNode() and again GetnodeX/GetNodeY
	4. To determine if a new node is required determine that !ReachedGoal() and
		the current position is the same as the current 'next tile to find' found in step 2

	Others
	1. If map is modified then call RedoAstarTileMap
	2. Use FreeTile to see if we can move to a tile (it is not a blocked tile)
	3. Use TileNum to return the tile number from a pixel location
*/
class AstarClass
{
	//node represents a tile on our map
    typedef struct NODE
    {
        long f;							// g+h (for calculating next/best node)
        long h;							// distance from node to destination
        int  g;							// cost of travel (distance from source to node)
        int  x;							// destination stored here
        int  y;							//
        int  NodeNum;					// tile number (y*mapwidth+x effectively)
        NODE *Parent;					// parent
        NODE *Child[ MAX_CHILDREN ];	// surrounding nodes
        NODE *NextNode;					// for linked list
    } NODE;

	//our linked list of nodes, FIFO
    typedef struct STACK
    {
        NODE  *NodePtr;					//pointer to the inserted node
        STACK *NextStackPtr;			//linked list
    } STACK;

private:
	//moved from public
    int Height;							//size of map
    int Width;
	int TileSize;						//purely for TileNumFromPixelLocation()
    int TotalSize;						//height*width
    int *TileMap;						//map to an array of the same size as the real map
										//array of 1's and 0's for open (0) or blocked (1)
    NODE  *OpenNode;					//where we haven't been
    NODE  *ClosedNode;					//where we've been
    NODE  *PathNode;					//current path node
    STACK *Stack;						//list of best nodes

	NODE *First;					// NW added, to go back to start of list

public:
    AstarClass( int *map, 
		int width, int height, 
		int tilesize);					//constructor. pass in map contain open/blocked items
    ~AstarClass();						//destructor. frees up everything
    void RedoAstarTileMap( int *map );	//recreate map array (in case original tile map is modified)
    bool NewPath( int source_x , 		//create and find a path. returns true if there is one
		int source_y , int dest_x , 
		int dest_y,  bool allowDiag=true );
    bool ReachedGoal();					//are we there yet
    void PathNextNode();				//next node in the path
    int NodeGetX();						//x,y of the current path node
    int NodeGetY();
	void NodeGoFirst();					//reset current path to the first one (NW)
    bool FreeTile( int x , int y );		//is tile at x/y (pixels) open (Available to be moved to)
    int TileNum( int x , int y );		//return array element of map using x/y in pixels

private:
    void FreeNodes();					//cleanup. called by destructor
    void FindPath( int source_x , 		//generate the path. called by newpath
		int source_y , 
		int dest_x , 
		int dest_y );
    NODE *ReturnBestNode();
	//these are called by findpath for creating the path
    void GenerateSuccessors( NODE *BestNode , int dest_x , int dest_y );
    void GenerateSucc( NODE *BestNode , int x , int y , int dest_x , int dest_y );
    NODE *CheckOPEN( int tilenum );
    NODE *CheckCLOSED( int tilenum );
    void Insert( NODE *Successor );
    void PropagateDown( NODE *Old );
    void Push( NODE *NODE );
    NODE *Pop();
	//stuff moved from public
    bool isPath;						//if true then we have a path from src to dst   
	//allegro specific stuff
	int distance( int x , int y );
	bool AllowDiagonalMovement;
};


#endif
